1. Field of the Invention
The present invention generally relates to an improved method for managing the operation of a cache memory in which both demand and prefetched data can be stored, and more particularly to an improved method for allocating space in the memory between demand and prefetched data on the basis of frequency of use.
2. Description of the Prior Art
In many data processing systems, a high-speed memory commonly called a "cache" is provided between the working memory of the central processing unit and a main memory. The cache enables a relatively fast access to a subset of data which has been previously transferred from main memory to the cache and thus improves the overall speed of the data processing system. Commonly, data transfers from main memory to cache are in pages or blocks of data and include both demand data pages and prefetched data pages. Demand data is data transferred to the cache as a result of a specific request from the central processing unit. When transferring demand data to the cache, it is advantageous to also transfer additional unrequested data (i.e. prefetched data) at the same time if it is likely the additional data will be soon requested.
When a cache is filled, data must be removed from the cache when new data is written in. Commonly, data cache management systems use the frequency of use of data in the cache as a criteria for selecting data to be removed from the cache. Least recently used (LRU) is a common criteria for replacement because of its simplicity and efficiency.
In the prior art, in replacing data in the cache, demand and prefetched data has been treated equally, without regard to the size of the incoming data of each type. Under this condition too large a portion (in terms of finding demanded data in cache) of the total cache storage capacity may be allocated to store prefetched data, especially when large amounts of data are prefetched in connection with each main memory demand data access.
U.S. Pat. No. 4,489,378, entitled Automatic Adjustment of the Quantity of Prefetch Data in a Disk Cache Operation, describes a dynamic mechanism to determine the number of prefetched data blocks in each disk cache operation. U.S. Pat. No. 4,807,110, entitled Prefetching System for a Cache Having a Second Directory for Sequentially Accessed Blocks, describes a way to select the data blocks for prefetching using two-level cache directories. Both these patents consider prefetching in the cache operation but use a conventional Least Recently Used (LRU) scheme for replacement.